package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test

/*
110. 平衡二叉树
https://leetcode.cn/problems/balanced-binary-tree/
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：
输入：root = []
输出：true
 */
class leetcode_110 {
    @Test
    fun test_1() {
        val root = TreeNode(3)
        val n9 = TreeNode(9)
        val n20 = TreeNode(20)
        val n15 = TreeNode(15)
        val n7 = TreeNode(7)
        root.left = n9
        root.right = n20
        n20.left = n15
        n20.right = n7

        val actual = isBalanced(root)
        val expected = true
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_2() {
        val root = TreeNode(1)
        val n2 = TreeNode(2)
        val n2_v2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n3_v2 = TreeNode(3)
        val n4 = TreeNode(4)
        val n4_v = TreeNode(4)

        root.left = n2
        root.right = n2_v2

        n2.left = n3
        n2.right = n3_v2

        n3.left = n4
        n3.right = n4_v

        val actual = isBalanced(root)
        val expected = false
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_3() {
        val actual = isBalanced(null)
        val expected = true
        Assert.assertEquals(expected, actual)
    }

    private fun isBalanced(root: TreeNode?): Boolean {
        /**
        1 后序遍历
        2 思路：
        求左右子树的高度： -1 表示 非平衡； 0  表示平衡
        左 ： 求左子树的高度，若-1，则返回-1
        右 ： 求右子树的高度，若-1，则返回-1
        中 ： 高度 = 若左右高度差的绝对值 > 1 ,则 -1 ，否则 左右高度的最大值
         */
        // 考察：高度差不大于1 ， 后序遍历 左右中 - 递归
        return getHeight(root) != -1
    }

    private fun getHeight(root: TreeNode?): Int {
        // 1 终止条件
        // -1  表示非平衡树
        if (null == root) {
            // 空树也是一个平衡二叉树
            return 0
        }
        // 2 左
        val leftHeight: Int = getHeight(root.left)
        if (leftHeight == -1) {
            return -1
        }
        // 3 右
        val rightHeight: Int = getHeight(root.right)
        if (rightHeight == -1) {
            return -1
        }
        // 4 中 - 求高度
        val height = if (Math.abs(leftHeight - rightHeight) > 1) {
            -1
        } else {
            1 + Math.max(leftHeight, rightHeight)
        }
        return height
    }
}
